Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Binary Tree Paths

Problem Statement

Given the root node of a binary tree, return all unique paths from the root node to the leaf node in any order.

Examples

Example 1:

  • Input: root = [1,2,3,null,null,4,5]
Image
  • Expected Output: ["1->2", "1->3->4", "1->3->5"]
  • Justification: The binary tree has one root-to-leaf path for the left child (1->2) and two for the right child, branching into 4 and 5 respectively.

Example 2:

  • Input: root = [5,3,6,2,4,null,null,1]
Image
  • Expected Output: ["5->3->2->1", "5->3->4", "5->6"]
  • Justification: There are three paths leading to leaf nodes: one through the left subtree down to 1, another through the left subtree to 4, and one path through the right subtree to 6.

Example 3:

  • Input: root = [2,null,3,null,4,null,5]
Image
  • Expected Output: ["2->3->4->5"]
  • Justification: There's only one path from the root to the leaf, cascading down the right children.

Solution

To solve this problem, we will employ a depth-first search (DFS) approach. DFS is particularly well-suited for this task because it allows us to explore each branch of the tree to its fullest extent (down to the leaf nodes) before backtracking. This ensures that we can collect all root-to-leaf paths efficiently. The algorithm works by traversing the tree from the root node, appending the value of each visited node to a path string, and recursively exploring all possible paths down to the leaf nodes. Once a leaf node is reached, the current path string is added to a list of paths. This method is applied recursively to each node's left and right children if they exist. By using DFS, we can guarantee that all paths are explored, and the use of recursion simplifies the traversal logic.

Our approach is effective because it aligns with the natural structure of binary trees, allowing us to leverage their hierarchical nature to efficiently navigate and record paths. DFS ensures that no node is missed and that each path is fully recorded before moving on to the next. This strategy is optimal for this problem because it minimizes unnecessary computations and visits each node exactly once, ensuring all unique root-to-leaf paths are captured.

Step-by-Step Algorithm

  1. Start at the Root: Begin the process with the root node of the binary tree.

  2. Initialize Paths List: Create an empty list to store the paths from the root to each leaf.

  3. Recursive Function - findPaths: Define a recursive function that takes the current node, the path so far (as a string), and the paths list as arguments. This function will be used to explore all possible paths from the root to the leaves.

  4. Base Case: In the recursive function, check if the current node is null. If it is, return immediately, as this path cannot lead to a leaf.

  5. Update Path: Append the current node's value to the path string. If the current node is not null, this means we are on a potential path to a leaf.

  6. Leaf Node Check: Check if the current node is a leaf (i.e., both its left and right children are null). If it is, add the current path to the paths list as a complete root-to-leaf path.

  7. Recursive Exploration: If the current node is not a leaf, recursively call the function on both the left and right children of the current node, if they exist. Before making the recursive call, add "->" to the path string to indicate the path's continuation.

  8. Return Paths: After all recursive calls complete, return the paths list containing all root-to-leaf paths found.

Algorithm Walkthrough

Image
  1. Start at Root (5): The path starts with "5".

  2. Move to Left Child (3): The path updates to "5->3". Since 3 is not a leaf, continue down.

  3. Explore Left of 3 (2): Path updates to "5->3->2". 2 is not a leaf; it has a right child.

    • Move to Right of 2 (1): Path is "5->3->2->1". 1 is a leaf, so add "5->3->2->1" to paths.
  4. Backtrack to 3 and Go Right (4): Path from 5 is "5->3". Now update path to "5->3->4". 4 is a leaf, so add "5->3->4" to paths.

  5. Backtrack to 5 and Move to Right Child (6): Now explore the right side of 5. The path is "5->6". Since 6 is a leaf, add "5->6" to paths.

Completed Paths:

  • By following the steps above, the algorithm discovers all paths:
    • "5->3->2->1"
    • "5->3->4"
    • "5->6"

These steps systematically explore each branch of the tree, ensuring that every unique root-to-leaf path is identified and recorded.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • : Where N is the number of nodes in the binary tree. In the worst case, we visit each node exactly once to either extend the path string or to backtrack.

Space Complexity:

  • : In the worst-case scenario, the space complexity is determined by the height of the binary tree, which influences the recursion stack depth. For a skewed binary tree (one where every parent node has only one child), the height of the tree can be N, leading to a space complexity of .
Binary Tree Paths (easy)
Sum of Root To Leaf Binary Numbers (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity:

Space Complexity: